1. Field of the Invention
The present invention relates to filter adaptation, for example in communications such as wireline communications.
2. State of the Art
Broadband communications solutions, such as HDSL2/G.SHDSL (High-Speed Digital Subscriber Line) are increasingly in demand. The ability to achieve high data rates (e.g., 1.5 Mbps and above) between customer premises and the telephone system central office over existing (unconditioned) telephone lines requires exacting performance. Various components of a high-speed modem that contribute to this performance require training, e.g., a timing section (PLL, or phase lock loop), an adaptive equalizer, an adaptive echo canceller. Typically, these components are all trained in serial fashion, one after another, during an initial training sequence in which known data is transmitted between one end of the line and the other.
Equalization is especially critical for HDSL2/G.SHDSL2 modems, which are required to operate over various line lengths and wire models and wirelines with and without bridge taps, with extremely divergent cross-talk scenarios. In general, intersymbol interference (ISI), which equalization aims to eliminate, is the limiting factor in XDSL communications. Hence, good equalization, characterized by the ability to accurately compute the optimal channel equalizer coefficients at the start-up phase of the modem and adaptively update those coefficients to accommodate any change in the level of cross-talk, is essential to any HDSL2/G.SHDSL system.
Known training methods for high-speed modems suffer from various disadvantages. Existing commercial products invariably use a Least Mean Squares (LMS) training algorithm, which is assumed to converge to an optimal training solution. The LMS algorithm is well-known and has generally been found to be stable and easy to implement. Conventional wisdom holds that the steady-state performance of LMS cannot be improved upon. Despite the widespread use of LMS and its attendant advantages, the adequacy of performance of LMS is being tested by the performance requirements of high-speed modems.
Nor are the alternatives to LMS particularly appealing. Other proposed algorithms have chiefly been of academic interest. The Recursive Least Squares (RLS) algorithm, for example, requires a far shorter training time than LMS (potentially one tenth the training time needed for LMS), but RLS entails exceedingly greater computational complexity. If N is the total number of taps in an adaptive filter, then the complexity of RLS is roughly N2, as compared to 2N for LMS. Also, RLS is less familiar and less tractable, suffering from stability problems.
An improved RLS algorithm (“fast RLS”) considerably reduces the computational complexity of RLS, from N2 to 28N. The original fast RLS algorithm is described in Falconer and Ljung, Application of Fast Kalman Estimation to Adaptive Equalization, IEEE Transaction on Communications, Vol. COM-26, No. 10, Oct. 1978, incorporated herein by reference. The fast RLS algorithm, however, requires that training be performed on contiguous data symbols. If training is performed “on-line,” then a high-performance processor is required to perform training computations at a rate sufficient to keep pace with the data rate, e.g., 1.5 Mbps or greater. Although the computational demand (demand for MIPs) “spikes up” during training, once training is completed, computational demands are modest. If training is performed “off-line” using stored data samples, then the processor need not keep up with the data rate, reducing peak performance requirements. However, a potentially long sequence of training data must be stored to satisfy the requirement of the algorithm for contiguous data, requiring a sizable memory. Again, the memory requirement, like training itself, is transient. Once training has been completed, the need for such a large memory is removed.
Apart from training, because communications channels vary over time, continuous or periodic filter adaptation is required. In the case of rapidly varying channel conditions, as in wireless communications and especially mobile wireless communications, and in the case of especially long filters relative to adaptation processing power, the use of RLS is indicated. In wireline communications, these conditions are typically not present. Even in the demanding case of HDSL2/G.SHDSL, filter lengths are moderate and channel variation can be considered to be slow. To applicant's knowledge, all wireline modems use LMS “on-line” for non-training filter adaptation.
Although the error criteria used by the LMS and RLS algorithms differ, the prevalent mathematical analysis of these algorithms suggests that the algorithms converge to the same solution, albeit at different rates. LMS uses mean squared error, a statistical average, as the error criterion. RLS eliminates such statistical averaging. Instead, RLS uses a deterministic approach based on squared error (note the absence of the word mean) as the error criterion. In effect, instead of the statistical averaging of LMS, RLS substitutes temporal averaging, with the result that the filter depends on the number of samples used in the computation. Although the prevalent mathematical analysis predicts equivalent performance for the two algorithms, the mathematical analysis for LMS is approximate only. Although a mathematically exact analysis of LMS has recently been advanced, the overwhelming complexity of that analysis defies any meaningful insight into the behavior of the algorithm and requires numeric solution.
There remains a need, particularly in high-speed wireline communications, for a filter adaptation solution the overcomes the foregoing disadvantages, i.e., that achieves greater optimality without requiring undue computational resources.